package main

/**
 * Definition for a QuadTree node.
 */
type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

func NewNode(Val bool, IsLeaf bool) *Node {
	return &Node{
		Val:         Val,
		IsLeaf:      IsLeaf,
		TopLeft:     nil,
		TopRight:    nil,
		BottomLeft:  nil,
		BottomRight: nil,
	}
}

func intersect(quadTree1 *Node, quadTree2 *Node) *Node {
	node1 := quadTree1
	node2 := quadTree2
	return _intersect(node1, node2)
}

func _intersect(node1 *Node, node2 *Node) *Node {
	if node1.IsLeaf {
		//node1是叶子，且为真，则或运算后结果全为真
		if node1.Val {
			return NewNode(true, true)
		}
		//node1是叶子，且为假，则或运算后结果是node2本身
		return node2
	}
	if node2.IsLeaf {
		//node1是叶子，处理方法与node1是叶子一样
		return _intersect(node2, node1)
	}

	c1 := _intersect(node1.TopLeft, node2.TopLeft)
	c2 := _intersect(node1.TopRight, node2.TopRight)
	c3 := _intersect(node1.BottomLeft, node2.BottomLeft)
	c4 := _intersect(node1.BottomRight, node2.BottomRight)
	//只有四个子树都是叶子，并且布尔值相同时，newNode才是叶子
	if c1.IsLeaf && c2.IsLeaf && c3.IsLeaf && c4.IsLeaf && c1.Val == c2.Val && c2.Val == c3.Val && c3.Val == c4.Val {
		return NewNode(c1.Val, true)
	}
	newNode := NewNode(true, false)
	newNode.TopLeft = c1
	newNode.TopRight = c2
	newNode.BottomLeft = c3
	newNode.BottomRight = c4
	return newNode
}

func main() {

}
